// 单词搜索

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_079 {
    public boolean result = false;

    public boolean exist(char[][] board, String word) {
        // 记录起始位置
        List<int[]> start = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0))
                    start.add(new int[] { i, j });
            }
        // 没有起始位置
        if (start.size() == 0)
            return false;
        // 对每个起始位置使用DFS
        for (int i = 0; i < start.size(); i++) {
            int[][] isVisit = new int[board.length][board[0].length];
            isVisit[start.get(i)[0]][start.get(i)[1]] = 1;
            DFS(start.get(i), 1, board, isVisit, word);
        }
        return result;
    }

    // 参数为目前的位置、目前的长度、数组、是否被访问、字符串。
    public void DFS(int[] cL, int currentLength, char[][] board, int[][] isVisit, String word) {
        // 如果目前的长度等于字符串长度则已经找到
        if (currentLength == word.length()) {
            result = true;
            return;
        }
        // 大于则未找到
        if (currentLength > word.length())
            return;
        // 上边位置，判断是否越界
        if (cL[0] - 1 >= 0 && isVisit[cL[0] - 1][cL[1]] == 0
                && board[cL[0] - 1][cL[1]] == word.charAt(currentLength)) {
            cL[0] = cL[0] - 1;
            isVisit[cL[0]][cL[1]] = 1;
            DFS(cL, currentLength + 1, board, isVisit, word);
            isVisit[cL[0]][cL[1]] = 0;
            cL[0] = cL[0] + 1;
        }
        // 下边位置，判断是否越界
        if (cL[0] + 1 < board.length && isVisit[cL[0] + 1][cL[1]] == 0
                && board[cL[0] + 1][cL[1]] == word.charAt(currentLength)) {
            cL[0] = cL[0] + 1;
            isVisit[cL[0]][cL[1]] = 1;
            DFS(cL, currentLength + 1, board, isVisit, word);
            isVisit[cL[0]][cL[1]] = 0;
            cL[0] = cL[0] - 1;
        }
        // 右边位置，判断是否越界
        if (cL[1] + 1 < board[0].length && isVisit[cL[0]][cL[1] + 1] == 0
                && board[cL[0]][cL[1] + 1] == word.charAt(currentLength)) {
            cL[1] = cL[1] + 1;
            isVisit[cL[0]][cL[1]] = 1;
            DFS(cL, currentLength + 1, board, isVisit, word);
            isVisit[cL[0]][cL[1]] = 0;
            cL[1] = cL[1] - 1;
        }
        // 左边位置，判断是否越界
        if (cL[1] - 1 >= 0 && isVisit[cL[0]][cL[1] - 1] == 0
                && board[cL[0]][cL[1] - 1] == word.charAt(currentLength)) {
            cL[1] = cL[1] - 1;
            isVisit[cL[0]][cL[1]] = 1;
            DFS(cL, currentLength + 1, board, isVisit, word);
            isVisit[cL[0]][cL[1]] = 0;
            cL[1] = cL[1] + 1;
        }
    }
}

public class Solution079 {

}
